BZOJ4407 于神之怒加强版 <莫比乌斯反演>

Problem

于神之怒加强版

Description

给下，计算的值。

Input

输入有多组数据，输入数据的第一行两个正整数，代表有组数据，的意义如上所示，下面第行到第行，每行为两个正整数，其意义如上式所示。

Output

对于每一个询问，输出一行一个数作为回答。

Sample Input

1 2
3 3

Sample Output

20

HINT

官方题解

标签：莫比乌斯反演

Solution

先套路转换出：

那么每次询问对于前半部分可以根号分块，随后需要计算后半部分的值，因而需要线筛预处理后半部分的值。

令，
由于和均为积性函数，因而也为积性函数。
那么就有

易知当时，均有，因此有

接下来考虑在线筛中如何处理。
首先，对于所有质数，均有。
而对于合数，假设当前筛到的数是，对于一个比它小的素数，有两种情况：

1. 若，设在分解质因数中的次数为，那么相比于而言，在含的约数中的次数都增加了，否则无贡献。因此增加了，这样总共扩大了倍，故；
2. 若，由积性函数可知。

这样就可以筛出的函数值，每次询问根号分块，总复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 5000000
#define MOD 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt k, cnt, ans, f[MAX_N+5], p[MAX_N+5], pri[MAX_N+5];	bool NotPri[MAX_N+5];
lnt PM(lnt x, lnt y) {if (!y) return 1LL; lnt ret = PM(x, y>>1); return (y&1) ? ret*ret%MOD*x%MOD : ret*ret%MOD;}
void init() {
    NotPri[1] = true, f[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, p[i] = PM(i, k), f[i] = p[i]-1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break; NotPri[i*pri[j]] = true;
            if (i%pri[j]) f[i*pri[j]] = f[i]*f[pri[j]]%MOD;
            else {f[i*pri[j]] = f[i]*p[pri[j]]%MOD; break;}
        }
    }
    for (int i = 2; i <= MAX_N; i++) (f[i] += f[i-1]) %= MOD;
}
int main() {
    int T;	read(T), read(k), init();
    while (T--) {
        lnt n, m;	read(n), read(m), ans = 0;
        for (lnt l = 1, r; l <= min(n, m); l = r+1)
            r = min(n/(n/l), m/(m/l)), (ans += (n/l)*(m/l)%MOD*(f[r]-f[l-1]+MOD)%MOD) %= MOD;
        printf("%lld\n", ans);
    }
    return 0;
}